COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00005 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A84.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, January 12, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
Take any locally constrained symbol system with $k$ variables, and $m$
constraints that apply to subsets of at most $b$ variables.  There are at
most ${k\choose b}$ such subsets, a polynomial of degree $b$.  The
constraints on each subset allow at most $2↑b$ different assignments of
values to the variables in a subset.  Construct a graph as follows:
for each constraint, say on variables $x, y, z$, and for each assignment
of values permitted by that constraint, say $x=a$, $y=b$, $z=c$, 
construct a vertex labeled $x=a$, $y=b$, $z=c$.  Two vertices
are contradictory if one includes $x=a$ and the other includes $x=b$.
In particular, any two vertices derived from the same constraint are
contradictory.  Let edges connect those pairs of vertices that are
not contradictory.

Suppose there is an assignment of values to variables that satisfies
all constraints.  For each constraint, there is one vertex containing a
subset of these assignments.  These vertices are not contradictory, and are a 
clique of size $m$.

Conversely, if there is a clique of size $m$, its vertices must include one
derived from each constraint, and must assign values satisfying each constraint
to all constrained variables.  Then any LCSS is transformable to a CLIQUE
problem, which is therefore NP-Complete.
\end